package com.code.test.dance;


/**
 * 206
 * 题意：反转一个单链表。
 * <p>
 * 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
 */
public class LinkFanzhuan {
    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        LinkNode second = new LinkNode(2);
        LinkNode third = new LinkNode(3);
        LinkNode n4 = new LinkNode(4);
        LinkNode n5 = new LinkNode(5);

        head.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);

        LinkNode node = reverse(head);

        int a = 2;
    }
    public static LinkNode reverse(LinkNode root) {
        //不能借助新的存储空间，只需要翻转指针

        LinkNode pre = null;
        LinkNode cur = root;
        while(cur!=null){
            //暂存下一个
            LinkNode tmp = cur.next;
            //当前的下一个是前一个
            cur.next = pre;
            //当前这个变成前一个，因为要往下移动，
            pre = cur;
            //更新当前这个，为之前暂存的下一个，往下推进
            cur = tmp;
        }

        return pre;


    }
}

